package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 84 柱状图中最大的矩形
 * @date 2024/12/24 11:42
 */
public class E84 {

    /**
     * 柱状图
     */
    static class Pillar {
        int index;
        int height;

        public Pillar() {

        }

        public Pillar(int index, int height) {
            this.index = index;
            this.height = height;
        }
    }

    /**
     * <h3>方法一：单调递增栈</h3>
     * @param heights 高度数组
     * @return 最大面积
     */
    public int largestRectangleArea(int[] heights) {
        LinkedList<Pillar> stack = new LinkedList<>();
        int maxArea = 0;
        int length = heights.length;
        // 遍历数组，push到递增栈里面，同时统计柱形的面积
        for (int i = 0; i < length; i++){
            while (!stack.isEmpty() && heights[i] < stack.peek().height){
                Pillar prev = stack.pop();
                // 如果pop后，栈为空，则当前索引之前没有比刚刚弹出来的柱子高度更低的了
                int width = stack.isEmpty() ? i : i - stack.peek().index - 1;
                maxArea = Math.max(maxArea, width * prev.height);
            }
            stack.push(new Pillar(i, heights[i]));
        }
        // 遍历结束后，栈里面剩下的元素，也需要处理
        while (!stack.isEmpty()){
            Pillar prev = stack.pop();
            int width = stack.isEmpty() ? length : length - stack.peek().index - 1;
            maxArea = Math.max(maxArea, width * prev.height);
        }
        return maxArea;
    }
}
